package com.cat.binaryTree;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/insufficient-nodes-in-root-to-leaf-paths/description/
 * @create 2025/9/14 18:54
 * @since JDK17
 */

public class Solution39 {
    int limit;

    int f(TreeNode root, int cur) {
        if (root == null) {
            return Integer.MIN_VALUE;
        }
        if (root.left == null && root.right == null) {
            return root.val;
        }
        int l = f(root.left, cur + root.val) + root.val;
        int r = f(root.right, cur + root.val) + root.val;
        if (l + cur < limit) {
            root.left = null;
        }
        if (r + cur < limit) {
            root.right = null;
        }
        return Math.max(l, r);
    }

    public TreeNode sufficientSubset2(TreeNode root, int limit) {
        this.limit = limit;
        f(root, 0);
        if (root.left == null && root.right == null) {
            return null;
        }
        return root;
    }

    public TreeNode sufficientSubset(TreeNode root, int limit) {
        if (root == null) {
            return null;
        }
        limit -= root.val;
        if (root.left == null && root.right == null) {  // 叶节点
            return limit > 0 ? null : root;
        }
        root.left = sufficientSubset(root.left, limit);
        root.right = sufficientSubset(root.right, limit);
        return root.left == null && root.right == null ? null : root;
    }
}
